package club.banyuan;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class Bst<E extends Comparable<E>> {
  private static class Node<E extends Comparable<E>> {
    private E item;
    private Node<E> left;
    private Node<E> right;

    public Node(E data) {
      item = data;
      left = right = null;
    }
  }

  // 树根
  private Node<E> root;

  public Bst() {
    root = null;
  }

  /**
   * 将data放入到以root为根的树中
   *
   * @param root - 当前的树根
   * @param data - 新的数据
   * @return - 成功/失败
   */
  private boolean innerAdd(Node<E> root, E data) {
    if (data.compareTo(root.item) < 0) {
      // data小于当前的节点， 需要在左边去添加
      if (root.left == null) {
        // root没有左子节点， 已经找到了插入的位置
        root.left = new Node<>(data);
        return true;
      } else {
        // root有left
        return innerAdd(root.left, data);
      }
    } else if (data.compareTo(root.item) > 0) {
      // data 大于当前节点的值， 需要在右边添加
      if (root.right == null) {
        root.right = new Node<>(data);
        return true;
      } else return innerAdd(root.right, data);
    } else {
      // data == root.item
      // 对于相同值的情况， 我们不做处理
      return false;
    }
  }

  /**
   * 在树中新增元素data
   *
   * @param data - 新增的元素
   * @return false - 已经存在这个节点，无法新增
   */
  public boolean add(E data) {
    // 如果是空树
    if (root == null) {
      root = new Node<>(data);
      return true;
    }
    // 不是空树, 从树根开始， 找到一个位置， 增加新的节点
    return innerAdd(root, data);
  }

  /**
   * 中序遍历二叉树的元素， 将他们放到一个集合中
   * <p>中序遍历 (左子树 -> 当前节点 -> 右子树)
   * <p>前序遍历 (当前节点 -> 左子树 -> 右子树)
   * <p>后序遍历 (左子树   * -> 右子树 -> 当前节点)
   */
  private void traverse(Node<E> root, Collection<E> collection) {
    if (root == null) return;
    if (root.left != null) traverse(root.left, collection);
    collection.add(root.item);
    if (root.right != null) traverse(root.right, collection);
  }

  // 返回e的父节点
  // 前提：root不能是e， 否则无法返回
  private Node<E> findParent(Node<E> root, E e) {
    if (root.item.compareTo(e) > 0) {
      if (root.left == null) {
        // e应该在root的左边， 但是root的左子树为空, 查找失败
        return null;
      } else {
        // e 在root的左边
        if (root.left.item.compareTo(e) == 0)
          // e是root的左子节点
          return root;
        else
          // root的左子节点不是e
          return findParent(root.left, e);
      }
    } else {
      // 应该在root的右边
      if (root.right == null) return null;
      else {
        if (root.right.item.compareTo(e) == 0) return root;
        else return findParent(root.right, e);
      }
    }
  }

  /**
   * 删除指定的节点
   *
   * @param e - 要删除的元素
   * @return 成功或失败
   */
  public boolean delete(E e) {
    // 0. 先要找到e的父节点
    // 1. e是叶子节点， 直接删除
    // 2. e只有一个子节点， 那么用它的子节点代替它
    // 3. 有两个子节点，选择右子树中最左边的节点来替换它
    if (root == null) return false;

    if (root.item.compareTo(e) == 0) {
      // 直接删除root
      if (root.left == null) {
        root = root.right;
      } else {
        if (root.right == null) root = root.left;
        else {
          // 左右都不为空
          var leftest = findLeft(root.right);
          var temp = leftest.item;
          delete(leftest.item);
          root.item = temp;
        }
      }
    } else {
      var parent = findParent(root, e);
      if (parent == null) {
        // 没有找到这个节点， 无法删除
        return false;
      } else {
        // 找到节点的父节点了
        boolean leftChild = true;
        Node<E> deleteNode;
        if (parent.left != null && parent.left.item.compareTo(e) == 0) {
          // 删除parent的左子节点
          deleteNode = parent.left;
        } else {
          // 删除parent的右子节点
          leftChild = false;
          deleteNode = parent.right;
        }

        if (deleteNode.left == null && deleteNode.right == null) {
          // 叶子节点
          if (leftChild) {
            parent.left = null;
          } else {
            parent.right = null;
          }
        } else if (deleteNode.right != null && deleteNode.left == null) {
          // 只有右子树
          if (leftChild) {
            parent.left = deleteNode.right;
          } else {
            parent.right = deleteNode.right;
          }
        } else if (deleteNode.right == null) {
          // 只有左子树
          if (leftChild) {
            parent.left = deleteNode.left;
          } else {
            parent.right = deleteNode.left;
          }
        } else {
          // 左右都不为空
          // 找到右子树的最左边节点，将其值赋值到deleteNode, 再删除这个最左边节点
          var leftest = findLeft(deleteNode.right);
          var temp = leftest.item;
          delete(leftest.item);
          deleteNode.item = temp;
        }
      }
    }
    return true;
  }

  // 查找root里面的最左边节点, 返回这个节点
  private Node<E> findLeft(Node<E> root) {
    var temp = root;
    while (temp.left != null) temp = temp.left;
    return temp;
  }

  @Override
  public String toString() {
    var list = new ArrayList<E>();
    traverse(root, list);
    return list.toString();
  }

  public List<E> toList() {
    var list = new ArrayList<E>();
    traverse(root, list);
    return list;
  }

  private Node<E> findParent2(Node<E> root, E e) {
    if (root.item.compareTo(e) == 0) return root;
    else if (root.item.compareTo(e) > 0) {
      if (root.left == null) return null;
      else if (root.left.item.compareTo(e) == 0) return root;
      else return findParent(root.left, e);
    } else {
      if (root.right == null) return null;
      else if (root.right.item.compareTo(e) == 0) return root;
      else return findParent(root.right, e);
    }
  }

  private Node<E> findLeftestParent(Node<E> root) {
    while (root.left.left != null) root = root.left;
    return root;
  }

  private Node<E> innerDelete(Node<E> root, E e) {
    if (root == null) return null;
    if (root.item.compareTo(e) == 0) {
      // 删除root节点
      if (root.left == null) return root.right;
      else if (root.right == null) return root.left;
      else {
        // 左右都有
        // 查找右子树最左节点
        if (root.right.left == null) {
          root.right.left = root.left;
          return root.right;
        } else {
          var leftestParent = findLeftestParent(root.right);
          var leftest = leftestParent.left;
          leftestParent.left = leftest.right;
          leftest.left = root.left;
          leftest.right = root.right;
          return leftest;
        }
      }
    } else if (root.item.compareTo(e) > 0) {
      // 从左子树中删除e
      root.left = innerDelete(root.left, e);
    } else {
      root.right = innerDelete(root.right, e);
    }
    return root;
  }

  public boolean delete2(E e) {
    if (root == null) return false;
    root = innerDelete(root, e);
    return root != null; // ??? 似乎有问题
  }
}
